1. Field of the Invention
This invention relates generally to multiple process dispatchers, also called schedulers, that are used by operating systems to allocate computer resources to processes, and particularly to such dispatchers or schedulers which employ some degree of randomness in selecting which process gets allocation of a resource as it becomes available, and most particularly to computer system instruction processor resources.
2. General Background
In large scale computer systems, especially ones which do transaction processing for many users, allocation of instruction processor time to various users and classes of users becomes problematic, especially where the operating system allows for classification of users (or the processes/software agents they are running) into priority groups. In such cases, if there is a fair amount of activity by relatively high priority user groups, the low priority groups may never, or at least not with sufficient probability, get the use of the instruction processor resource. Tasks that must be done but do not warrant high priority usage group classification, such as batch clean-up tasks, for example, may not get executed at all, thus ultimately impairing the value of the computer system to the business concern which has the batch tasks attempting to run with the transaction processing tasks.
In an article titled “Lottery Scheduling: Flexible Proportional-Share Resource Management” (Proceedings of the First Symposium on Operating Systems Design and Implementation, 1994, PP 1–11; incorporated herein by reference, the authors described a method for lottery scheduling which could be applied to this problem. However by itself it is insufficient to run a scheduler in any large scale computer system. A public critique of the article was given by Michael Courage on Feb. 22, 1996 at http://www.eecs.harvard.edu/˜courage/cs261/critique (also incorporated by this reference).
A problem we encountered was that the requirement to recalculate the allocation scheme constantly was unacceptable in a computer system doing an average of four thousand scheduling allocations in each second.
In the applicant's computer systems, multiprocessor computer systems are common, and the use of the scheduler described in this application may be better understood in the context of such systems, although it is not a requirement for understanding the functioning of the invention herein. Because the multiprocessor systems may have numerous task queues, the scheduler executable which does the allocation may be activated for each one of these queues. Reference may be had to the inventor's patent application Ser. No. 09/920,023, filed Aug. 1, 2001, hereby incorporated by this reference in its entirety, in which the invention herein can be used to function in the capacity of the dispatcher or dispatcher program which schedules or allocates the tasks on the various switching queues for the various instruction processors. Of course, even single processor systems and systems with single task queues may benefit from the inventive features described in the instant patent.
Accordingly, there is a need to develop a more efficacious scheduler for large-scale computer systems. This is especially true for computer systems that handle many users doing transaction processing and that are also handling other tasks at the same general time.